Quantifying Inefficiency of Fair Cost-Sharing Mechanisms for Sharing Economy

摘要

Sharing economy is a distributed peer-to-peer economic paradigm, which givesrise to a variety of social interactions for economic purposes. One fundamentaldistributed decision-making process is coalition formation for sharing certainreplaceable resources collaboratively, for example, sharing hotel rooms amongtravelers, sharing taxi-rides among passengers, and sharing regular passesamong users. Motivated by the applications of sharing economy, this paperstudies a coalition formation game subject to the capacity of $K$ participantsper coalition. The participants in each coalition are supposed to split theassociated cost according to a given cost-sharing mechanism. A stable coalitionstructure is established when no group of participants can opt out to formanother coalition that leads to lower individual payments. We quantify theinefficiency of distributed decision-making processes under a cost-sharingmechanism by the strong price of anarchy (SPoA), comparing a worst-case stablecoalition structure and a social optimum. In particular, we derive SPoA forcommon fair cost-sharing mechanisms (e.g., equal-split, proportional-split,egalitarian and Nash bargaining solutions of bargaining games, and usage basedcost-sharing). We show that the SPoA for equal-split, proportional-split, andusage based cost-sharing (under certain conditions) is $\Theta(\log K)$,whereas the one for egalitarian and Nash bargaining solutions is $O(\sqrt{K}\log K)$. Therefore, distributed decision-making processes under common faircost-sharing mechanisms induce only moderate inefficiency.